package 单周赛.history;

/**
 *
 */
public class 第299场单周赛 {

    public static void main(String[] args) {

        int[][] gird = {{2, 0, 0, 1}, {0, 3, 1, 0}, {0, 5, 2, 0}, {4, 0, 0, 2}};
        System.out.println(checkXMatrix(gird));

        System.out.println(countHousePlacements(10000));

    }

    public static boolean checkXMatrix(int[][] grid) {
        int n = grid.length;
        for (int row = 0; row < n; row++) {
            for (int column = 0; column < n; column++) {
                if (row + column == n - 1 || row == column) {
                    if (grid[row][column] == 0) return false;
                } else if (grid[row][column] != 0) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 6100. 统计放置房子的方式数
     * 一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。
     * 现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。
     * 注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。
     * <p>
     * 动态规划+快速乘
     * 因为当前放置房子只与前一个房子有关，空间优化，用两个数组位置来存储
     * 放置 [0,i] 房子的全部方式
     * 1，dp[0] 表示当前不放置房子的全部方式数目，如果不放置房子，那么前面一个位置放置和不放置都行
     * dp[i][0] = dp[i-1][0] + dp[i-1][1]
     * 2，dp[1] 表示当前放置房子的全部方式数目，如果当前位置放置了房子，那么前面一个位置必须不放置房子
     * dp[i][1] = dp[i-1][0]
     * <p>
     * 放置了一排房子之后，另一排的总方式数目也为，dp[0] + dp[1]
     * 结果:
     * (dp[0] + dp[1])(dp[0] + dp[1])
     *
     * @param n
     * @return
     */
    public static int countHousePlacements(int n) {
        long[] dp = new long[2];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            long preNoSet = dp[0];
            long preYesSet = dp[1];
            dp[0] = preNoSet + preYesSet > 1000000007 ? preNoSet + preYesSet - 1000000007 : preNoSet + preYesSet;
            dp[1] = preNoSet;
        }
        long ans = 0;
        long a = dp[0] + dp[1];
        long b = a;
        while (a > 0) {
            if ((a & 1) == 1) ans = (ans + b) % 1000000007;
            a >>= 1;
            b <<= 1;
        }
        return (int) ans;
    }

}
